
Namespace std
    Public Class hashmap(Of keyT As IComparable(Of keyT), valueT,
                            HASH_SIZE As _int64)
        Inherits hashmap(Of keyT, valueT, HASH_SIZE, _to_uint32(Of keyT))
    End Class

    Public Class hashmap(Of keyT As IComparable(Of keyT), valueT, _
                            HASH_SIZE As _int64, KEY_TO_INDEX As _to_uint32(Of keyT))
        Implements ICloneable

        Private Shared ReadOnly _end As iterator = Nothing
        Private Shared ReadOnly hashSize As Int64 = 0
        Private Shared ReadOnly _keyToIndex As KEY_TO_INDEX = Nothing
        Private _data() As map(Of keyT, valueT)

        Public Class iterator
            Inherits map(Of keyT, valueT).iterator
            Private _index As UInt32
            Private _container As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX) = Nothing

            Friend Function index() As UInt32
                Return _index
            End Function

            Friend Function container() As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX)
                Return _container
            End Function

            Public Function key() As keyT
                Dim rtn As keyT = Nothing
                copy(rtn, (+p).first)
                Return rtn
            End Function

            Public Function value() As valueT
                Dim rtn As valueT = Nothing
                copy(rtn, (+p).second)
                Return rtn
            End Function

            Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
                If Not MyBase.traversal(prev) Then
                    If Not prev Then
                        _index = _container.nextIndex(_index)
                        If hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX).valid_index(_index) Then
                            p = convertor.cast(Of pointer(Of map(Of keyT, valueT).node)) _
                                              (_container.data(_index, False).begin()).instance()
                        End If

                        Return p <> _container.end()
                    Else
                        _index = _container.prevIndex(_index)
                        If hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX).valid_index(_index) Then
                            p = convertor.cast(Of pointer(Of map(Of keyT, valueT).node)) _
                                (_container.data(_index, False).rbegin()).instance()
                        End If

                        Return p <> _container.rend()
                    End If
                Else
                    Return True
                End If
            End Function

            Public Sub New(ByVal container As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX), _
                           ByVal index As Int64, _
                           ByVal that As map(Of keyT, valueT).iterator)
                MyBase.New(that)
                _container = container
                _index = index
            End Sub
        End Class

        Private Shared Function valid_index(ByVal index As UInt32) As Boolean
            Return index < hashSize
        End Function

        Private Shared Function invalid_index(ByVal index As UInt32) As Boolean
            Return Not valid_index(index)
        End Function

        Private Function data(ByVal index As Int64, Optional ByVal autoInsert As Boolean = True) As map(Of keyT, valueT)
            If _data(index) Is Nothing AndAlso autoInsert Then
                _data(index) = New map(Of keyT, valueT)()
            End If
            Return _data(index)
        End Function

        Private Function empty(ByVal i As Int64) As Boolean
            assert(valid_index(i))
            Return data(i, False) Is Nothing OrElse data(i).empty()
        End Function

        Private Function prevIndex(ByVal this As UInt32) As UInt32
            Do
                If this = 0 Then
                    this = maxUInt32
                Else
                    this -= 1
                End If
                If invalid_index(this) Then
                    Exit Do
                End If
            Loop Until Not empty(this)

            Return this
        End Function

        Private Function nextIndex(ByVal this As Int32) As Int32
            Do
                this += 1
                If invalid_index(this) Then
                    Exit Do
                End If
            Loop Until Not empty(this)

            Return this
        End Function

        Public Function rbegin() As iterator
            Dim rtn As iterator = Nothing
            Dim index As Int32 = prevIndex(hashSize)
            If valid_index(index) Then
                Return New iterator(Me, index, data(index).rbegin())
            End If
            Return rend()
        End Function

        Public Function begin() As iterator
            Dim rtn As iterator = Nothing
            Dim index As Int32 = nextIndex(-1)
            If valid_index(index) Then
                Return New iterator(Me, index, data(index).begin())
            End If
            Return [end]()
        End Function

        Public Function [end]() As iterator
            Return _end
        End Function

        Public Function [rend]() As iterator
            Return _end
        End Function

        Public Sub clear()
            ReDim _data(hashSize - 1)
        End Sub

        Shared Sub New()
            _end = New iterator(Nothing, maxUInt32, map(Of keyT, valueT).shared_end())
            _keyToIndex = alloc(Of KEY_TO_INDEX)()
            hashSize = +(alloc(Of HASH_SIZE)())
        End Sub

        Private Shared Function keyToIndex(ByVal k As keyT) As UInt32
            Return _keyToIndex(k) Mod hashSize
        End Function

        Public Sub New()
            clear()
        End Sub

        Default Public Property _D(ByVal k As keyT) As valueT
            Get
                Return data(keyToIndex(k))(k)
            End Get
            Set(ByVal value As valueT)
                data(keyToIndex(k)).insert(k, value)
            End Set
        End Property

        Public Function insert(ByVal k As keyT, ByVal v As valueT) As iterator
            Dim index As Int32 = npos
            index = keyToIndex(k)
            Return New iterator(Me, index, data(index).insert(k, v))
        End Function

        Public Function insert(ByVal other As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX)) As Boolean
            If other Is Nothing Then
                Return False
            Else
                For i As Int64 = 0 To hashSize - 1
                    If Not other.data(i, False) Is Nothing Then
                        data(i).insert(other.data(i))
                    End If
                Next
                Return True
            End If
        End Function

        Public Function find(ByVal k As keyT) As iterator
            Dim index As Int32 = npos
            index = keyToIndex(k)
            If data(index, False) Is Nothing Then
                Return [end]()
            Else
                Return New iterator(Me, index, data(index).find(k))
            End If
        End Function

        Public Function empty() As Boolean
            For i As Int64 = 0 To hashSize - 1
                If Not empty(i) Then
                    Return False
                End If
            Next
            Return True
        End Function

        Public Function [erase](ByVal it As iterator) As Boolean
            If it Is Nothing Then
                Return False
            Else
                assert(object_compare(it.container(), Me) = 0)
                Return data(it.index()).erase(it)
            End If
        End Function

        Public Function Clone() As Object Implements System.ICloneable.Clone
            Dim rtn As hashmap(Of keyT, valueT, HASH_SIZE, KEY_TO_INDEX) = Nothing
            rtn = alloc(Me)
            Dim i As Int32
            For i = 0 To hashSize - 1
                If Not _data(i) Is Nothing Then
                    copy(rtn._data(i), _data(i))
                End If
            Next

            Return rtn
        End Function
    End Class
End Namespace
